package org.example.leetCode;

/**
 * 796. 旋转字符串
 * 给定两个字符串, s 和 goal。如果在若干次旋转操作之后，s 能变成 goal ，那么返回 true 。
 * s 的 旋转操作 就是将 s 最左边的字符移动到最右边。
 * 例如, 若 s = 'abcde'，在旋转一次之后结果就是'bcdea' 。
 */
public class Code796 {

    public boolean rotateString(String s, String goal) {
        String haystack=s+s;
        String needle=goal;
        if(s.length()!=goal.length()){
            return false;
        }
        int m = needle.length();
        if (m == 0) return true;
        char[] p = needle.toCharArray();
        char[] ss = haystack.toCharArray();
        int[] next = new int[m + 1];
        next[0] = 0;
        //构建next数组
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && p[i] != p[j]) {
                j = next[j - 1];
            }
            //p[i]==p[j]相等，则取j++对应的数
            //不等，则j一定是0，取next[0]，即0
            if (p[i] == p[j]) j++;
            next[i] = j;
        }
        //kmp匹配过程
        for (int i = 0, j = 0; i < ss.length; i++) {
            while (j > 0 && ss[i] != p[j]) {
                j = next[j - 1];
            }
            if (ss[i] == p[j]) j++;
            if (j == m) return true;
        }
        return false;
    }


}
